Average-Case Analysis

Tags: #◇CCDSALG #◇Algorithms #◇Computer Science #◇Computational Complexity #◇Efficiency #◇Algorithm Design Paradigms #◇Analysis of Algorithms #◇Probability #◇Data Structures #◇Time Complexity #◇Space Complexity

---

◇Overview

Average-case analysis determines the expected running time of an algorithm over all possible inputs of size $n$, weighted by their probability.

◇Key Concepts

Requires a probability distribution over inputs Expected value of running time: $T_{\text{avg}}(n) = E[T(I)]$ Often assumes uniform distribution (all inputs equally likely) Harder to compute than ◇Worst-Case Analysis

◇Details / Theory

Definition

The average-case running time is the expected number of operations over all possible inputs of size $n$:

$T_{\text{avg}}(n) = \sum_{\text{all inputs } I \text{ of size } n} P(I) \cdot T(I)$

where $P(I)$ is the probability of encountering input $I$.

When Average-Case is Useful

When you want a more realistic measure of performance than ◇Worst-Case Analysis. When the worst case is rare and doesn’t reflect typical usage. Example: Quick Sort has $O(n^2)$ worst-case but $O(n \log n)$ average-case — in practice it’s fast.

Example: Linear Search

Searching for a target in an unsorted array of $n$ elements (assuming target is in the array, each position equally likely):

$T_{\text{avg}}(n) = \frac{1}{n} \sum_{i=1}^{n} i = \frac{1}{n} \cdot \frac{n(n+1)}{2} = \frac{n+1}{2} = O(n)$

On average, we check about half the array.

Comparison of Analysis Types

◇Common Pitfalls

Assuming uniform distribution when it doesn’t hold — the analysis depends on the distribution. Confusing average-case with "typical" case — average-case is a mathematical expectation. Forgetting that average-case analysis is significantly harder than worst-case.

◇Summary

TL;DR — Average-case analysis computes the expected running time across all possible inputs weighted by probability. It gives a more realistic performance picture but requires knowledge of the input distribution.

◇Links

Related: ◇Worst-Case Analysis — ◇Best-Case Analysis — ◇Time Complexity — ◇Running Time — ◇Algorithm Analysis Source / Reference: Handout 01

◇References & Navigation

• Previous Topic: ◇Asymptotic Notation
• Next Topic: ◇Best-Case Analysis
• Related Notes: ◇Best-Case Analysis, ◇Worst-Case Analysis